package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * dp
 * 312. 戳气球
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/13 13:50
 */
public class MaxCoins {

    public static void main(String[] args) {
        MaxCoins test = new MaxCoins();

        // 167
        int[] arr = {3,1,5,8};

        int i = test.maxCoins(arr);
        System.out.println(i);
    }

    public int maxCoins(int[] nums) {
        int length = nums.length + 2;
        int [] item = new int[length];
        item[0] = 1;
        item[length - 1] = 1;
        System.arraycopy(nums, 0, item, 1, length - 2);
        int[][]arr = new int[length][length];
        for (int i = length - 3; i >= 0; i--) {
            for (int j = i + 2; j < length; j++) {
                int max = 0;
                for (int k = i + 1; k <= j - 1; k++) {
                    max = Math.max(max, item[k] * item[i] * item[j] + arr[i][k]  + arr[k][j]);
                }
                arr[i][j] = max;
            }
        }
        return arr[0][length - 1];
    }

}
